home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_400 / 420_02 / sqrmaze.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1994-02-16  |  24.0 KB  |  622 lines
  1. #include <iostream.h>
  2. #include "oracle.h"
  3. #include "cell.h"
  4. #include "titillat.h"
  5. #include "sqrmaze.h"
  6.  
  7. #define TRUE -1
  8. #define FALSE 0
  9.  
  10. typedef cell *cell_ptr;
  11.  
  12. maze::maze(int row_count,int column_count,int thickness_of_wall,char *seed)
  13. //      Contruct a maze having "row_count" rows and "column_count" columns of
  14. // rooms.  The walls should be "thickness_of_wall" (bricks) thick.  A different
  15. // (8 character of less) "seed" generally yields a different maze.
  16.   {
  17.     struct
  18.       {
  19.          int row_num;
  20.          int column_num;
  21.       }  delta [4];
  22.     int  mud_filled_room_found;
  23.     struct
  24.       {
  25.          int row_num;
  26.          int column_num;
  27.       }  next;
  28.     char wall [24] [4];
  29.     char wall_to_check;
  30.     char wall_num;
  31.     char way_out;
  32.  
  33.     // Allocate a two dimensional array of rooms.
  34.     num_rows=row_count;
  35.     num_columns=column_count;
  36.     if (memory_allocated=((room=new cell_ptr[num_rows]) != NULL))
  37.       {
  38.         int row_num=0;
  39.         while ((memory_allocated) && (row_num < num_rows))
  40.           if (memory_allocated=((room[row_num]=new cell [num_columns]) != NULL))
  41.             row_num++;
  42.         if (! memory_allocated)
  43.           {
  44.             while (row_num)
  45.               delete [] room[--row_num];
  46.             delete [] room;
  47.             cerr << "Fatal error:  cannot allocate maze." << '\n';
  48.           }
  49.       }
  50.     if (memory_allocated)
  51.       {
  52.          wall_thickness=thickness_of_wall;
  53.          // Set up the directions by which a room can be exited.
  54.          delta[0].row_num=-1;    // north
  55.          delta[0].column_num=0;
  56.          delta[1].row_num=0;     // west
  57.          delta[1].column_num=-1;
  58.          delta[2].row_num=1;     // south
  59.          delta[2].column_num=0;
  60.          delta[3].row_num=0;     // east
  61.          delta[3].column_num=1;
  62.          int order_num=0;
  63.          // Set up the 4! orders in which the wall of a room can be accessed.
  64.          for (int wall_num_1=0; wall_num_1 < 4; wall_num_1++)
  65.            for (int wall_num_2=0; wall_num_2 < 4; wall_num_2++)
  66.              if (wall_num_2 != wall_num_1)
  67.                for (int wall_num_3=0; wall_num_3 < 4; wall_num_3++)
  68.                  if ((wall_num_3 != wall_num_2)
  69.                  &&  (wall_num_3 != wall_num_1))
  70.                    for (int wall_num_4=0; wall_num_4 < 4; wall_num_4++)
  71.                      if ((wall_num_4 != wall_num_3)
  72.                      &&  (wall_num_4 != wall_num_2)
  73.                      &&  (wall_num_4 != wall_num_1))
  74.                        {
  75.                          wall[order_num][wall_num_4]='\0';
  76.                          wall[order_num][wall_num_3]='\1';
  77.                          wall[order_num][wall_num_2]='\2';
  78.                          wall[order_num][wall_num_1]='\3';
  79.                          order_num++;
  80.                        }
  81.          titillator_ptr=new titillator;    
  82.          order_selector=new oracle(&seed[0],order_num);
  83.          row_selector=new oracle(&seed[0],num_rows);
  84.          column_selector=new oracle(&seed[0],num_columns); 
  85.          int finished=FALSE;
  86.          // Generate mazes until you have one that is hard to solve.
  87.          do
  88.            {
  89.               // Pick a starting room.
  90.               first.row_num=row_selector->random_number();
  91.               first.column_num=column_selector->random_number();
  92.               current.row_num=first.row_num;
  93.               current.column_num=first.column_num;
  94.               // Excavate the starting room.
  95.               room[current.row_num][current.column_num].mark_floor(' ');
  96.               // Pick the order in which the walls of the starting room will be
  97.               // considered.
  98.               room[current.row_num][current.column_num].set_order(
  99.                order_selector->random_number());
  100.               titillator_ptr->titillate();
  101.               // Excavate rooms until there are no more to excavate.
  102.               do
  103.                 {
  104.                    mud_filled_room_found=FALSE;
  105.                    // Find an adjacent room (not yet considered) that needs
  106.                    // excavating.
  107.                    do
  108.                      {
  109.                         wall_num=room[current.row_num][
  110.                          current.column_num].next_wall_num();
  111.                         if (wall_num < '\4')
  112.                           {
  113.                              wall_to_check=wall[room[current.row_num][
  114.                               current.column_num].order_to_check()][wall_num];
  115.                              if (room[current.row_num][
  116.                               current.column_num].wall_up(wall_to_check))
  117.                                {
  118.                                   next.row_num=current.row_num
  119.                                    +delta[wall_to_check].row_num;
  120.                                   if ((next.row_num >= 0)
  121.                                   &&  (next.row_num < num_rows))
  122.                                     {
  123.                                       next.column_num=current.column_num
  124.                                        +delta[wall_to_check].column_num;
  125.                                       if ((next.column_num >= 0)
  126.                                       &&  (next.column_num < num_columns))
  127.                                         {
  128.                                            if (room[next.row_num][
  129.                                             next.column_num].mark() 
  130.                                             == 'M')
  131.                                              mud_filled_room_found=TRUE;
  132.                                         }
  133.                                     }
  134.                                }
  135.                           }
  136.                      }
  137.                    while ((wall_num < '\4')
  138.                    &&     (! mud_filled_room_found));
  139.                    if (mud_filled_room_found)
  140.                    // an adjacent room needs excavating
  141.                      {
  142.                         // Exit the current room, knocking down a wall.
  143.                         room[current.row_num][
  144.                          current.column_num].knock_down_wall(wall_to_check);
  145.                         way_out=char(((int) wall_to_check+2)%4);
  146.                         // Enter the adjacent room, knocking down a wall.
  147.                         room[next.row_num][next.column_num].knock_down_wall(
  148.                          way_out);
  149.                         // Record how to return to the previous room.
  150.                         room[next.row_num][next.column_num].set_way_out(
  151.                          way_out);
  152.                         current.row_num=next.row_num;
  153.                         current.column_num=next.column_num;
  154.                         // Excavate the room.
  155.                         room[current.row_num][current.column_num].mark_floor(' ');
  156.                         // Select the order in which the walls of the room will
  157.                         // be considered.
  158.                         room[current.row_num][current.column_num].set_order(
  159.                          order_selector->random_number());
  160.                      }
  161.                    else
  162.                    // no adjacent room needs excavating
  163.                      {
  164.                         if ((first.row_num != current.row_num)
  165.                         ||  (first.column_num != current.column_num))
  166.                         // not in starting room
  167.                           {
  168.                              // Go back to the room from which you entered
  169.                              // the current room.
  170.                              next.row_num=current.row_num+delta[
  171.                               room[current.row_num][
  172.                               current.column_num].way_back()].row_num;
  173.                              next.column_num=current.column_num+delta[
  174.                               room[current.row_num][
  175.                               current.column_num].way_back()].column_num;
  176.                              current.row_num=next.row_num;
  177.                              current.column_num=next.column_num;
  178.                           }
  179.                      }
  180.                 }
  181.               while ((first.row_num != current.row_num)
  182.               ||     (first.column_num != current.column_num)
  183.               ||     (wall_num < '\4'));
  184.               if (maze_okay()) // Maze is hard to solve.
  185.                 finished=TRUE;
  186.               else             // Prepare to try another maze.
  187.                 for (int row_num=0; row_num < num_rows; row_num++)
  188.                   for (int column_num=0; column_num < num_columns; column_num++)
  189.                     room[row_num][column_num].reinitialize();
  190.            }
  191.          while (! finished);
  192.          // Knock down walls blocking the entrance and exit to the maze.
  193.          room[0][0].knock_down_wall(0);
  194.          room[num_rows-1][num_columns-1].knock_down_wall(2);
  195.  
  196.          delete column_selector;
  197.          delete row_selector;
  198.          delete order_selector;
  199.          delete titillator_ptr;
  200.       }
  201.   }
  202.  
  203. maze::~maze()
  204.   {
  205.     if (memory_allocated)
  206.       {
  207.         // Free the two dimensional array of rooms.
  208.         for (int row_num=0; row_num < num_rows; row_num++)
  209.           delete [] room[row_num];
  210.         delete [] room;
  211.       }
  212.   }
  213.  
  214. int maze::maze_okay()
  215.   {
  216.     int  adjacency;
  217.     struct
  218.       {
  219.          int row_num;
  220.          int column_num;
  221.       }  delta [4];
  222.     struct
  223.       {
  224.          int row_num;
  225.          int column_num;
  226.       }  next;
  227.     int  num_rooms_in_solution;
  228.     int  passage_found;
  229.     struct
  230.       {
  231.          int row_num;
  232.          int column_num;
  233.       }  previous;
  234.     int  result;
  235.     struct
  236.       {
  237.          int row_num;
  238.          int column_num;
  239.       }  saved;
  240.     char wall_to_check;
  241.     char way_out;
  242.  
  243.     // Set up the directions by which a room can be exited.
  244.     delta[0].row_num=-1;    // north
  245.     delta[0].column_num=0;
  246.     delta[1].row_num=0;     // west
  247.     delta[1].column_num=-1;
  248.     delta[2].row_num=1;     // south
  249.     delta[2].column_num=0;
  250.     delta[3].row_num=0;     // east
  251.     delta[3].column_num=1;
  252.     // Solve the maze.
  253.  
  254.     // Start at the entrance.
  255.     current.row_num=0;
  256.     current.column_num=0;
  257.     // Mark the room as part of the solution.
  258.     room[current.row_num][current.column_num].mark_floor('S');
  259.     num_rooms_in_solution=1;
  260.     // Prepare to consider all the walls of the room.
  261.     room[current.row_num][current.column_num].zero_wall_to_check();
  262.     // Try rooms until you get to the exit.
  263.     do
  264.       {
  265.         // Find a passage (not yet considered) out of the current room leading
  266.         // to a room not part of the proposed solution.
  267.         passage_found=FALSE;
  268.         do
  269.           {
  270.             wall_to_check
  271.              =room[current.row_num][current.column_num].next_wall_num();
  272.             if (wall_to_check < '\4')
  273.               {
  274.                  if (! (room[current.row_num][
  275.                   current.column_num].wall_up(wall_to_check)))
  276.                    {
  277.                       next.row_num=current.row_num
  278.                        +delta[wall_to_check].row_num;
  279.                       if ((next.row_num >= 0)
  280.                       &&  (next.row_num < num_rows))
  281.                         {
  282.                           next.column_num=current.column_num
  283.                            +delta[wall_to_check].column_num;
  284.                           if ((next.column_num >= 0)
  285.                           &&  (next.column_num < num_columns))
  286.                             {
  287.                                if (room[next.row_num][
  288.                                 next.column_num].mark() 
  289.                                 == ' ')
  290.                                  passage_found=TRUE;
  291.                             }
  292.                         }
  293.                    }
  294.               }
  295.           }
  296.         while ((! passage_found) && (wall_to_check < '\4'));
  297.         if (passage_found)
  298.         // passage to room not currently part of proposed solution found
  299.           {
  300.             // Enter the room.
  301.             current.row_num=next.row_num;
  302.             current.column_num=next.column_num; 
  303.             // Record the way back to the previous room.
  304.             way_out=char(((int) wall_to_check+2)%4);
  305.             room[current.row_num][current.column_num].set_way_out(way_out);
  306.             // Mark the room as part of the proposed solution.
  307.             room[current.row_num][current.column_num].mark_floor('S');
  308.             num_rooms_in_solution++;
  309.             // Prepare to consider all the walls of the room.
  310.             room[current.row_num][current.column_num].zero_wall_to_check();
  311.           }
  312.         else
  313.         // dead end
  314.           {
  315.             // Mark current room as not part of proposed solution.
  316.             room[current.row_num][current.column_num].mark_floor(' ');
  317.             num_rooms_in_solution--;
  318.             // Go back to the room from which this room was entered.
  319.             next.row_num=current.row_num+delta[
  320.              room[current.row_num][current.column_num].way_back()].row_num;
  321.             next.column_num=current.column_num+delta[
  322.              room[current.row_num][current.column_num].way_back()].column_num;
  323.             current.row_num=next.row_num;
  324.             current.column_num=next.column_num;
  325.           }
  326.       }
  327.     while((current.row_num != num_rows-1)
  328.     ||    (current.column_num != num_columns-1));
  329.  
  330.     // Now that the maze is solved, calculate the number of rooms in the
  331.     // solution (or outside the maze) that are adjacent to the rooms in
  332.     // the solution.
  333.     adjacency=0;
  334.     previous.row_num=-1;
  335.     previous.column_num=0;
  336.     current.row_num=0;
  337.     current.column_num=0;
  338.     do
  339.       {
  340.         for (wall_to_check='\0'; wall_to_check < '\4'; wall_to_check++)
  341.           if (room[current.row_num][current.column_num].wall_up(wall_to_check))
  342.             {
  343.                next.row_num=current.row_num+delta[wall_to_check].row_num;
  344.                if ((next.row_num >= 0)
  345.                &&  (next.row_num < num_rows))
  346.                  {
  347.                     next.column_num=current.column_num
  348.                      +delta[wall_to_check].column_num;
  349.                     if ((next.column_num >= 0)
  350.                     &&  (next.column_num < num_columns))
  351.                       {
  352.                          if (room[next.row_num][next.column_num].mark() == 'S')
  353.                            adjacency++;
  354.                       }
  355.                     else
  356.                       adjacency++;
  357.                  }
  358.                else
  359.                  adjacency++;
  360.             }
  361.           else
  362.             {
  363.                next.row_num=current.row_num+delta[wall_to_check].row_num;
  364.                if ((next.row_num >= 0)
  365.                &&  (next.row_num < num_rows))
  366.                  {
  367.                    next.column_num=current.column_num
  368.                     +delta[wall_to_check].column_num;
  369.                    if ((next.column_num >= 0)
  370.                    &&  (next.column_num < num_columns))
  371.                      {
  372.                         if ((room[next.row_num][next.column_num].mark() == 'S')
  373.                         &&  ((previous.row_num != next.row_num)
  374.                           || (previous.column_num != next.column_num)))
  375.                           {
  376.                             saved.row_num=next.row_num;
  377.                             saved.column_num=next.column_num;
  378.                           }
  379.                      }
  380.                  }
  381.             }
  382.         previous.row_num=current.row_num;
  383.         previous.column_num=current.column_num;
  384.         current.row_num=saved.row_num;
  385.         current.column_num=saved.column_num;
  386.       }
  387.     while((current.row_num != num_rows-1)
  388.     ||    (current.column_num != num_columns-1));
  389.     for (wall_to_check='\0'; wall_to_check < '\4'; wall_to_check++)
  390.       if (room[current.row_num][current.column_num].wall_up(wall_to_check))
  391.         {
  392.            next.row_num=current.row_num+delta[wall_to_check].row_num;
  393.            if ((next.row_num >= 0)
  394.            &&  (next.row_num < num_rows))
  395.              {
  396.                 next.column_num=current.column_num
  397.                  +delta[wall_to_check].column_num;
  398.                 if ((next.column_num >= 0)
  399.                 &&  (next.column_num < num_columns))
  400.                   {
  401.                      if (room[next.row_num][next.column_num].mark() == 'S')
  402.                        adjacency++;
  403.                   }
  404.                 else
  405.                   adjacency++;
  406.              }
  407.            else
  408.              adjacency++;
  409.         }
  410.  
  411.     // The maze is hard to solve (from the outside) if more than a third of its
  412.     // rooms are part of its solution and rooms not part of its solution tend to
  413.     // be next to rooms in its solution.
  414.     if ((3*num_rooms_in_solution >= num_rows*num_columns)
  415.     &&  (9*adjacency <= 8*num_rooms_in_solution))
  416.       result=TRUE;
  417.     else
  418.       result=FALSE;
  419.     return result;
  420.   }
  421.  
  422. int maze::external_to_maze(double x,double y)
  423. //      Return TRUE if and only if a point (x,y) is external to the maze.
  424.   {
  425.     int result;
  426.  
  427.     if (y < 0.0)
  428.       result=TRUE;
  429.     else
  430.       if (y > double(3*wall_thickness*num_columns+wall_thickness-1))
  431.         result=TRUE;
  432.       else
  433.         if (x < 0.0)
  434.           result=TRUE;
  435.         else
  436.           if (x > double(3*wall_thickness*num_rows+wall_thickness-1))
  437.             result=TRUE;
  438.           else
  439.             result=FALSE;
  440.     return result;
  441.   }
  442.  
  443. double maze::f(double x,double y)
  444. //      Return 6.0*wall_thickness if a point (x,y) is on a wall, 0.0 otherwise.
  445.   {
  446.     double z;
  447.  
  448.     if (y < 0.0)
  449.       z=0.0;
  450.     else
  451.       if (y > double(3*wall_thickness*num_columns+wall_thickness-1))
  452.         z=0.0;
  453.       else
  454.         if (x < 0.0)
  455.           z=0.0;
  456.         else
  457.           if (x > double(3*wall_thickness*num_rows+wall_thickness-1))
  458.             z=0.0;
  459.           else
  460.             {  
  461.               int tem_int=int(y);
  462.               int column_num=tem_int/(3*wall_thickness);
  463.               int y_mod_3_wall_thickness=tem_int-3*wall_thickness*column_num;
  464.               tem_int=int(x);
  465.               int row_num=tem_int/(3*wall_thickness);
  466.               int x_mod_3_wall_thickness=tem_int-3*wall_thickness*row_num;
  467.               if (row_num < num_rows)
  468.                 if (column_num < num_columns)
  469.                   if (x_mod_3_wall_thickness < wall_thickness)
  470.                     if (y_mod_3_wall_thickness < wall_thickness)
  471.                     // northwest corner
  472.                       z=1.0;
  473.                     else
  474.                     // north wall
  475.                       if (room[row_num][column_num].wall_up('\0'))
  476.                         z=1.0;
  477.                       else
  478.                         z=0.0;
  479.                   else
  480.                     if (y_mod_3_wall_thickness < wall_thickness)
  481.                     // west wall
  482.                       if (room[row_num][column_num].wall_up('\1'))
  483.                         z=1.0;
  484.                       else
  485.                         z=0.0;
  486.                     else
  487.                     // in room
  488.                       z=0.0;
  489.                 else
  490.                   // east most wall
  491.                   z=1.0;
  492.               else
  493.                 // south most wall
  494.                 if (column_num < num_columns)
  495.                   if (y_mod_3_wall_thickness < wall_thickness)
  496.                     // southwest corner
  497.                     z=1.0;
  498.                   else
  499.                     // south wall
  500.                     if (room[num_rows-1][column_num].wall_up('\2'))
  501.                       z=1.0;
  502.                     else
  503.                       z=0.0;
  504.                 else
  505.                   // southeast most corner
  506.                   z=1.0;
  507.             }
  508.     return z*double(6*wall_thickness);
  509.   }
  510.  
  511. int maze::part_of_solution(double x,double y)
  512. //      Return TRUE if and only if a point (x,y) is on a wall outlining the
  513. // solution to the maze.
  514.   {
  515.     int result;
  516.  
  517.     if (y < 0.0)
  518.       result=FALSE;
  519.     else
  520.       if (y > double(3*wall_thickness*num_columns+wall_thickness-1))
  521.         result=FALSE;
  522.       else
  523.         if (x < 0.0)
  524.           result=FALSE;
  525.         else
  526.           if (x > double(3*wall_thickness*num_rows+wall_thickness-1))
  527.             result=FALSE;
  528.           else
  529.             {  
  530.               int tem_int=int(y);
  531.               int column_num=tem_int/(3*wall_thickness);
  532.               int y_mod_3_wall_thickness=tem_int-3*wall_thickness*column_num;
  533.               tem_int=int(x);
  534.               int row_num=tem_int/(3*wall_thickness);
  535.               int x_mod_3_wall_thickness=tem_int-3*wall_thickness*row_num;
  536.               if (row_num < num_rows)
  537.                 if (column_num < num_columns)
  538.                   if (x_mod_3_wall_thickness < wall_thickness)
  539.                     if (y_mod_3_wall_thickness < wall_thickness)
  540.                       // northwest corner
  541.                       if ((room[row_num][column_num].mark() == 'S')
  542.                       ||  ((row_num > 0) 
  543.                         && (room[row_num-1][column_num].mark() == 'S'))
  544.                       ||  ((column_num > 0)
  545.                         && (room[row_num][column_num-1].mark() == 'S'))
  546.                       ||  ((row_num > 0) && (column_num > 0)
  547.                         && (room[row_num-1][column_num-1].mark() == 'S')))
  548.                         result=TRUE;
  549.                       else
  550.                         result=FALSE;
  551.                     else
  552.                       // north wall
  553.                       if (room[row_num][column_num].wall_up('\0'))
  554.                         if ((room[row_num][column_num].mark() == 'S')
  555.                         ||  ((row_num > 0)
  556.                           && (room[row_num-1][column_num].mark() == 'S')))
  557.                           result=TRUE;
  558.                         else
  559.                           result=FALSE;
  560.                       else
  561.                         result=FALSE;
  562.                   else
  563.                     if (y_mod_3_wall_thickness < wall_thickness)
  564.                     // west wall
  565.                       if (room[row_num][column_num].wall_up('\1'))
  566.                         if ((room[row_num][column_num].mark() == 'S')
  567.                         ||  ((column_num > 0)
  568.                           && (room[row_num][column_num-1].mark() == 'S')))
  569.                           result=TRUE;
  570.                         else
  571.                           result=FALSE;
  572.                       else
  573.                         result=FALSE;
  574.                     else
  575.                     // in room
  576.                       result=FALSE;
  577.                 else
  578.                   // east most wall
  579.                   if (x_mod_3_wall_thickness < wall_thickness)
  580.                     // northeast corner
  581.                     if ((room[row_num][num_columns-1].mark() == 'S')
  582.                     ||  ((row_num > 0)
  583.                       && (room[row_num-1][num_columns-1].mark() == 'S')))
  584.                       result=TRUE;
  585.                     else
  586.                       result=FALSE;
  587.                   else
  588.                     // east wall
  589.                     if (room[row_num][num_columns-1].mark() == 'S')
  590.                       result=TRUE;
  591.                     else
  592.                       result=FALSE;
  593.               else
  594.                 // south most wall
  595.                 if (column_num < num_columns)
  596.                   if (y_mod_3_wall_thickness < wall_thickness)
  597.                     // southwest corner
  598.                     if ((room[num_rows-1][column_num].mark() == 'S')
  599.                     ||  ((column_num > 0)
  600.                       && (room[num_rows-1][column_num-1].mark() == 'S')))
  601.                       result=TRUE;
  602.                     else
  603.                       result=FALSE;
  604.                   else
  605.                     // south wall
  606.                     if (room[num_rows-1][column_num].wall_up('\2'))
  607.                       if (room[num_rows-1][column_num].mark() == 'S')
  608.                         result=TRUE;
  609.                       else
  610.                         result=FALSE;
  611.                     else
  612.                       result=FALSE;
  613.                 else
  614.                   // southeast most corner
  615.                   if (room[num_rows-1][num_columns-1].mark() == 'S')
  616.                     result=TRUE;
  617.                   else
  618.                     result=FALSE;
  619.             }
  620.     return result;
  621.   }
  622.